#include<stdio.h>
int majorityElement(int* nums, int numsSize){
    int key = nums[0];
    int count = 0;
    for (int i = 0; i < numsSize; i++)
    {
        if(nums[i] == key)
            count++;
        else
            count--;
        
        if(count <= 0)
        {
            key = nums[i+1];
        }
        
    }
    return key;
}
int main()
{
	int arr[]={3,1,1,1,1,3,4,1,5};
	printf("%d",majorityElement(arr,9));
	return 0;
}
